#include "lex.h"
#include "symbolTable.h"
#include <iostream>
#include <cstdio>
using std::cin;
using std::cout;
using std::endl;

using namespace cp;
namespace{
inline int min(int a, int b){
	return a < b ? a : b;
}
inline int max(int a, int b){
	return a < b ? b : a;
}

inline int min(int a, int b, int c){
	return min(a, min(b, c));
}
inline int max(int a, int b, int c){
	return max(a, max(b, c));
}


struct Trie{
	int symID;
	Trie* next[128];
	Trie():symID(-1){memset(next, 0, sizeof(next));}
	void insert(int id, const char* p){
		if (!*p) {symID = id; return;}
		Trie* &tar = next[(int)*p];
		if (!tar) tar = new Trie;
		tar->insert(id, ++p);
	}
	int getIDr(const char*& p){
		auto& tar = next[(int)*p];
		return tar ? tar->getIDr(++p) : symID;
	}
	int getID(const char *p){
		return getIDr(p);
	}
}root, keyWordTrie;

int next[19][128];
int symID[19];
int curChar;

std::map<int,void(*)(const char*, Token*)> tokenProcess;
void integer(const char* p, Token *token){
	int t = 0;
	while (*p) t = t*10 + *p++-'0';
	token->cont = (void*)t;
}
void identifier(const char*p, Token *token){
	char *buf = new char[strlen(p)+1];
	strcpy(buf, p);
	token->cont = buf;
}
void BEGIN(const char*p, Token *token){
}
void END(const char*p, Token *token){
}
void popDel(){
	delete ts.top();
	ts.pop();
}

const char* label[] = {
	"Program",         "SubProgram",    "ConstDeclaration", "ConstDefinition",
	"VarDeclaration",  "Statement",     "Expression",       "Condition",
	"Integer",         "Identifier",    "PROGRAM",          "BEGIN",
	"END",             "CONST",         "VAR",              "WHILE",
    "DO",              "IF",            "THEN",             "(",
    ")",               "*",             "+",                ",",
    "-",               "/",             ":=",               ";",
    "<",               "<=",            "<>",               "=",
    ">",               ">=",            "EOP",
};

int pri[] = {
	0, 0, 0, 0,
	0, 0, 0, 0,
	0, 1, 0, 1,
	0, 0, 0, 1,
	0, 1, 0, 0,
	0, 2, 0, 0,
	0, 2, 0, 1,
	0, 0, 0, 0,
	0, 0, 0,
};

const static int MAX_INT = 0xfffffff;

struct ExpInfo{
	int id, b, e;
	ExpInfo(int _id = 0, int _b = MAX_INT, int _e = 0):
		id(_id), b(_b), e(_e){}
};

struct ConInfo{
	int b, e;
};

struct StateInfo{
	int b, e;
	StateInfo(int _b = MAX_INT, int _e = 0):
		b(_b), e(_e){}
};

bool E2PE(){
	void *cont = ts.top()->cont;
	popDel();

	ts.top()->cont = cont;
	ts.top()->symID = root.getID("Expression");
	return true;
}

bool E2ME(){
	int id = getTempID();
	ExpInfo *info = (ExpInfo*)ts.top()->cont;
	popDel();

	int t = genQuad(Minus, id, info->id, 0);
	info->b = min(info->b, t);
	info->e = t;
	info->id = id;

	ts.top()->cont = info;
	ts.top()->symID = root.getID("Expression");
	return true;
}

bool P2PrIdSPEoP(){
	return true;
}

bool SP2VDSP(){
	popDel();
	ts.top()->symID = root.getID("SubProgram");
	return true;
}

bool SP2CDfSP(){
	popDel();
	ts.top()->symID = root.getID("SubProgram");
	return true;
}

bool SP2S(){
	ts.top()->symID = root.getID("SubProgram");
	return true;
}

bool CDc2CCdf(){
	popDel();
	ts.top()->symID = root.getID("ConstDeclaration");
	return true;
}

bool CDc2CDcComCDf(){
	popDel();
	popDel();
	return true;
}

bool CDf2IdAInt(){
	int value = (int)ts.top()->cont, id;
	popDel();
	popDel();
	char *key = (char*)ts.top()->cont;
	if (!defineConst(key, value, id)) return false;
	delete key;
	ts.top()->symID = root.getID("ConstDefinition");
	return true;
}

bool VD2VDSimi(){
	popDel();
	return true;
}

bool VD2VDComId(){
	char* key = (char*)ts.top()->cont;
	int id;
	if (!declareVar(key, id)) return false;
	popDel();
	popDel();
	delete key;
	return true;
}

bool VD2VI(){
	char* key = (char*)ts.top()->cont;
	int id;
	if (!declareVar(key, id)) return false;
	popDel();
	ts.top()->symID = root.getID("VarDeclaration");
	delete key;
	return true;
}

bool S2WCDS(){
	StateInfo* sinfo = (StateInfo*)ts.top()->cont;
	popDel();
	popDel();
	ConInfo* cinfo = (ConInfo*)ts.top()->cont;
	popDel();

	int t = genQuad(JMP, cinfo->b, 0, 0);

	sinfo->b = min(sinfo->b, cinfo->b, t);
	sinfo->e = max(sinfo->e, cinfo->e, t);

	getQuad(cinfo->e-1).resID = cinfo->e+1;
	getQuad(cinfo->e).resID = t+1;

	Token* top = ts.top();
	top->symID = root.getID("Statement");
	top->cont = sinfo;
	delete cinfo;
	return true;
}

bool S2ICTS(){
	StateInfo* sinfo = (StateInfo*)ts.top()->cont;
	popDel();
	popDel();
	ConInfo* cinfo = (ConInfo*)ts.top()->cont;
	popDel();

	sinfo->b = min(sinfo->b, cinfo->b);
	sinfo->e = max(sinfo->e, cinfo->e);

	getQuad(cinfo->e-1).resID = cinfo->e+1;
	getQuad(cinfo->e).resID = sinfo->e+1;

	Token* top = ts.top();
	top->symID = root.getID("Statement");
	top->cont = sinfo;

	delete cinfo;
	return true;
}

bool S2SS(){
	StateInfo *rt = (StateInfo*)ts.top()->cont;
	popDel();
	StateInfo *lf = (StateInfo*)ts.top()->cont;
	lf->b = min(lf->b, rt->b);
	lf->e = max(lf->e, rt->e);
	delete rt;
	return true;
}

bool S2BSE(){
	popDel();
	void *cont = ts.top()->cont;
	popDel();
	ts.top()->cont = cont;
	return true;
}

bool S2Semi(){
	StateInfo *info = new StateInfo;
	ts.top()->cont = info;
	ts.top()->symID = root.getID("Statement");
	return true;
}

bool S2IAE(){
	ExpInfo *info = (ExpInfo*)ts.top()->cont;
	popDel();
	popDel();
	Token* top = ts.top();
	const char* key = (const char*)top->cont;
	int id;
	if (!getVarID(key, id)) return false;
	int pos = genQuad(Assign_Var, id, info->id, 0);

	StateInfo *sinfo = new StateInfo;
	sinfo->b = min(info->b, pos);
	sinfo->e = max(info->e, pos);

	top->cont = sinfo;
	top->symID = root.getID("Statement");

	delete info;
	delete key;
	return true;
}

bool C2EOpE(int op){
	ExpInfo* rt = (ExpInfo*)ts.top()->cont;
	popDel();
	popDel();
	Token* top = ts.top();
	ExpInfo* lf = (ExpInfo*)top->cont;
	ConInfo* res = new ConInfo;
	int t1 = genQuad(op, 0, lf->id, rt->id);
	int t2 = genQuad(JMP, 0, 0, 0);

	res->b = min(lf->b, rt->b, t1);
	res->e = max(lf->e, rt->e, t2);
	delete lf;
	delete rt;
	top->symID = root.getID("Condition");
	top->cont = res;
	return true;
}

bool C2ELEE(){
	return C2EOpE(JLE);
}

bool C2ELE(){
	return C2EOpE(JL);
}

bool C2EGEE(){
	return C2EOpE(JGE);
}

bool C2EGE(){
	return C2EOpE(JG);
}

bool C2ENeE(){
	return C2EOpE(JNE);
}

bool C2EEE(){
	return C2EOpE(JE);
}

bool E2Id(){
	Token* top = ts.top();
	int id;
	const char* key = (const char*)top->cont;
	if (!cp::getVarID(key, id)) return false;
	ExpInfo *info = new ExpInfo(id);
	top->symID = root.getID("Expression");
	top->cont = info;
	delete key;
	return true;
}

bool E2Int(){
	Token* top = ts.top();
	int id = getTempID();
	int t = genQuad(QuadOp::Assign_Int, id, (int)top->cont, 0);
	ExpInfo *info = new ExpInfo(id, t, t);
	top->cont = info;
	top->symID = root.getID("Expression");
	return true;
}

bool E2BEB(){
	popDel();
	void *cont = ts.top()->cont;
	popDel();
	ts.top()->cont = cont;
	ts.top()->symID = root.getID("Expression");
	return true;
}

bool E2EOpE(int op){
	ExpInfo* rt = (ExpInfo*)ts.top()->cont;
	popDel();
	popDel();
	Token* top = ts.top();
	ExpInfo* lf = (ExpInfo*)top->cont;
	int resID = getTempID();
	int t = genQuad(op, resID, lf->id, rt->id);
	lf->id = resID;
	lf->b = min(lf->b, rt->b, t);
	lf->e = max(lf->e, rt->e, t);
	delete rt;
	return true;
}

bool E2EAE(){
	return E2EOpE(Add);
}
bool E2ESE(){
	return E2EOpE(Sub);
}
bool E2EME(){
	return E2EOpE(Mul);
}
bool E2EDE(){
	return E2EOpE(Div);
}

Action actions[ProdCount] = {
	P2PrIdSPEoP,	SP2CDfSP,	SP2VDSP,	SP2S,
	CDc2CCdf,	CDc2CDcComCDf,	CDf2IdAInt,	VD2VI,
	VD2VDComId,	VD2VDSimi,	S2Semi,	S2IAE,	S2BSE,
	S2SS,	S2ICTS,	S2WCDS,	E2EAE,	E2ESE,	E2EME,
	E2EDE,	E2PE,	E2ME,	E2Id,	E2Int,	E2BEB,
	C2EEE,	C2ENeE,	C2ELE,	C2ELEE,	C2EGE,	C2EGEE,
};

int pps[ProdCount] = {
	0,	0,	0,	0,	0,	0,	1,	0,	0,	1,	0,
	0,	0,	2,	4,	4,	1,	1,	3,	3,	4,	4,
	0,	0,	0,	0,	0,	0,	0,	0,	0,
};

const char* pss[ProdCount] = {
	"Program -> PROGRAM Identifier SubProgram EOP",
	"SubProgram -> ConstDefinition SubProgram",
	"SubProgram -> VarDeclaration SubProgram",
	"SubProgram -> Statement",
	"ConstDeclaration -> CONST ConstDefinition",
	"ConstDeclaration -> ConstDeclaration , ConstDefinition",
	"ConstDefinition -> Identifier := Integer",
	"VarDeclaration -> VAR Identifier",
	"VarDeclaration -> VarDeclaration , Identifier",
	"VarDeclaration -> VarDeclaration ;",
	"Statement -> ;",
	"Statement -> Identifier := Expression",
	"Statement -> BEGIN Statement END",
	"Statement -> Statement Statement",
	"Statement -> IF Condition THEN Statement",
	"Statement -> WHILE Condition DO Statement",
	"Expression -> Expression + Expression",
	"Expression -> Expression - Expression",
	"Expression -> Expression * Expression",
	"Expression -> Expression / Expression",
	"Expression -> + Expression",
	"Expression -> - Expression",
	"Expression -> Identifier",
	"Expression -> Integer",
	"Expression -> ( Expression )",
	"Condition -> Expression = Expression",
	"Condition -> Expression <> Expression",
	"Condition -> Expression < Expression",
	"Condition -> Expression <= Expression",
	"Condition -> Expression > Expression",
	"Condition -> Expression >= Expression",
};

void buildNext(){
	const char* p = "()*+,-/:;<=>";
	for (int i = 1; *p; ++p)
		next[0][(int)*p] = i++;
	next[8]['='] = 13;
	next[10]['='] = 14;
	next[10]['>'] = 15;
	next[12]['='] = 16;
	for (int i = '0'; i <= '9'; ++i){
		next[0][i] = next[17][i] = 17;
		next[18][i] = 18;
	}
	for (int i = 'a'; i <= 'z'; ++i)
		next[0][i] = next[18][i] = 18;

	for (int i = 'A'; i <= 'Z'; ++i)
		next[0][i] = next[18][i] = 18;
	const char* symLable[] = {
		"", "(", ")", "*", "+", ",", "-", "/", ":", ";",
		"<", "=", ">", ":=", "<=", "<>", ">=",
		"Integer", "Identifier",
	};
	for (int i = 0; i < 19; ++i)
		symID[i] = root.getID(symLable[i]);
	tokenProcess[root.getID("Integer")] = integer;
	tokenProcess[root.getID("Identifier")] = identifier;
	tokenProcess[root.getID("BEGIN")] = BEGIN;
	tokenProcess[root.getID("END")] = END;
}

void nextAvailChar(){
	while (curChar != EOF && isLayout(curChar))
		curChar = nextChar();
}

Token* nextToken(){
	static char buf[1024];
	int state = 0;
	char *p = buf;
	nextAvailChar();
	*p = curChar;
	int row = ::row, col = ::col;
	while (next[state][curChar]){
		state = next[state][curChar];
		curChar = *++p = nextChar();
	}
	*p = 0;
	int id = keyWordTrie.getID(buf);
	if (id < 0) id = symID[state];
	if (id < 0) {
		if (curChar == EOF) id = SymbolCount-1;
		else {
			sprintf(errMsg, "语法错");
			return 0;
		};
	}
	Token* ret = new Token;
	ret->symID = id;
	ret->row = row;
	ret->col = col;

	auto iter = tokenProcess.find(id);
	if (iter != tokenProcess.end()) iter->second(buf, ret);
	return ret;
}

}

bool cp::beginParse(){
	for(;;){
		Token*p = nextToken();
		if (!p) {cout << "词法错\n当前为" << row << "行" << col << "列" << endl; return false;}
		switch(doNextToken(p)){
		case -1:
			cout << "语法错： " << errMsg << endl;
			if (ts.empty()) return false;
			p = ts.top();
			cout << "当前为" << p->row << "行" << p->col << "列" << endl;
			return false;
		case 1:
			cout << "解析完毕" << endl;
			return true;
		}
	}
	return false;
}

void cp::initSymbolAndProds(){
	symbols.clear();
	prods.clear();

	for (int i = 0; i < SymbolCount; ++i){
		symbols.push_back(Symbol(label[i], pri[i], i >= NonTermCount));
		root.insert(i, label[i]);
		cout << symbols[i] << endl;
	}

	for (int i = 0; i < ProdCount; ++i){
		const char* p = pss[i];
		Production prod;
		prod.left = root.getIDr(p);
		p += 3;
		for(;;){
			p = skipLayout(p);
			if (!*p) break;
			int t = root.getIDr(p);
			if (t < 0) printf("err\n");
			else prod.right.push_back(t);
		}
		prod.action = actions[i];
		prod.pri = pps[i];
		prods.push_back(prod);
	}

	for (Production& prod : prods)
		cout << prod << endl;

	buildNext();
	const char* KeyWords[] = {
		"PROGRAM", "BEGIN", "END", "CONST",
		"VAR", "WHILE", "DO", "IF", "THEN"
	};
	for (int i = 0; i < 9; ++i)
		keyWordTrie.insert(root.getID(KeyWords[i]), KeyWords[i]);
	curChar = nextChar();
	pushTable();
}


















